package codeTop;

import java.util.Arrays;

public class sort {

    //快速排序
    public void quickSort(int[] nums,int low,int high){
        if (low < high) {
            int partition = partition(nums, low, high);
            quickSort(nums,low,partition-1);
            quickSort(nums,partition+1,high);
        }
    }
    public int partition(int[] nums,int low,int high){
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low]= pivot;
        return low;
    }


    //堆排序(大根堆为例)
    public void heapSort(int[] nums){
        buildHeap(nums,nums.length);
        for (int i = nums.length-1;i >0 ; i--) {
            swap(nums,0,i);
            adjustHeap(nums,0,i);
        }
    }
    public void buildHeap(int[] nums,int len){
        for (int i = len/2-1;i>=0;i--){
            adjustHeap(nums,i,len);
        }
    }
    public void adjustHeap(int[] nums,int head,int len){
        for (int i = head*2+1;i<len;i= i*2+1){
            //左优先
            if (i+1<len && nums[i]<nums[i+1]){
                i = i+1;
            }
            if (nums[i]>nums[head]){
                swap(nums,i,head);
                head = i;
            }
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,4,2,5,6,1,23,4,100,78,66,3,12,17};
        sort sort = new sort();
//        sort.quickSort(nums,0, nums.length-1);
        sort.heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
